#encoding: utf-8

import time
from constants import *

ANCESTRO_S = -1


class Camino_aumentante:
    # El camino aumentante es más o menos lo que hacemos a mano. Tenemos una
    # lista con tuplas de a 4 campos, uno para la posición en la cola del
    # ancestro, otro para el valor del flujo y el último para saber si es
    # backward o forward. Además, como no podemos borrar la cola porque
    # después es el corte minimal, tenemos un entero pos que marca el elemento
    # que estoy revisando en este momento.
    def __init__(self):
        self.vertices = set()
        self.cola = []
        self.cola.append(S)
        self.dict = {S: [ANCESTRO_S, INF, FORW]}
        self.pos = 0
        self.valor = 0
        self.esta_t = False
        self.camino_como_string = ',t'
        self.pos_t = -1

    def add(self, elem, cap_sobrante, backward):
        """Esta función agrega el elemento elem a la cola. En flujo debe estar
        la capacidad sobrante del lado ancestro-elem. El ancestro será el
        objeto que está actualmente en el visor.

        >>> c = Camino_aumentante()
        >>> c.add(3, 10, BACK)
        >>> c.cola == [(S, ANCESTRO_S, INF, FORW), (3, 0, 10, BACK)]
        True
        >>> c.add(2, 5, FORW)
        >>> c.cola == [(S, ANCESTRO_S, INF, FORW), (3, 0, 10, BACK), \
            (2, 0, 5, FORW)]
        True
        >>> c.quitar()
        >>> c.add(1, 4, FORW)
        >>> c.cola == [(S, ANCESTRO_S, INF, FORW), (3, 0, 10, BACK), \
            (2, 0, 5, FORW), (1, 1, 4, FORW)]
        True
        >>> c.pos_t
        3
        """
        elem_actual = self.cola[self.pos]
        minimo = min(cap_sobrante, self.dict[elem_actual][1])
        self.cola.append(elem)
        self.vertices.add(elem)
        self.dict[elem] = [elem_actual, minimo, backward]
        if elem == T:
            self.valor = minimo
            self.esta_t = True
            self.pos_t = len(self.cola) - 1

    def esta_en_cola(self, x):
        """Devuelve True si x está en la cola del camino aumentante.

        >>> c = Camino_aumentante()
        >>> c.esta_en_cola(0)
        True
        >>> c.add(3, 10, BACK)
        >>> c.esta_en_cola(3)
        True
        >>> c.esta_en_cola(4)
        False
        """
        return (x in self.vertices)

    def elemento(self):
        """Devuelve el elemento que estoy viendo.

        >>> c = Camino_aumentante()
        >>> c.add(3, 10, BACK)
        >>> c.add(2, 5, FORW)
        >>> c.elemento()
        0
        >>> c.quitar()
        >>> c.elemento()
        3
        >>> c.add(1, 4, FORW)
        >>> c.elemento()
        3
        >>> c.quitar()
        >>> c.elemento()
        2
        >>> c.quitar()
        >>> c.elemento()
        1
        """
        assert(len(self.cola) > self.pos)
        return self.cola[self.pos]

    def quitar(self):
        """Adelanto el visor"""
        self.pos = self.pos + 1

    def camino_de_ancestros(self):
        """Devuelve el una lista con el camino desde t hasta s. Implicitamente
        también construye el string para luego imprimir. t debe estar en la
        cola.

        >>> c = Camino_aumentante()
        >>> c.add(3, 10, FORW)
        >>> c.add(2, 5, FORW)
        >>> c.quitar()
        >>> c.add(4, 3, BACK)
        >>> c.quitar()
        >>> c.quitar()
        >>> c.add(1, 4, FORW)
        >>> c.camino_de_ancestros()
        [1, 4, 3, 0]
        >>> c.camino_como_string
        's,3<4,t'
        """
        l = {0: T}
        self.camino_como_string = ',t'
        # p almacena las posiciones de los ancestros en la cola.

        p = self.dict[T][0]  # p tiene al ancestro de t, porque después de que
                            # se agrega no se quitan más elementos.
        i = 1

        while p != S:  # no agrego s todavía
            l[i] = p
            if not self.es_backward(p):
                self.camino_como_string = ',' + str(p) + \
                    self.camino_como_string
            else:
                self.camino_como_string = '<' + str(p) + \
                    self.camino_como_string
            p = self.dict[p][0]  # en p almaceno al ancestro.
            i += 1

        l[i] = S
        self.camino_como_string = 's' + self.camino_como_string
        return l

    def camino_vacio(self):
        """Devuelve True si quedan elemento en la cola por revisar

        >>> c = Camino_aumentante()
        >>> c.camino_vacio()
        False
        >>> c.add(3, 10, BACK)
        >>> c.add(2, 5, FORW)
        >>> c.quitar()
        >>> c.camino_vacio()
        False
        >>> c.quitar()
        >>> c.quitar()
        >>> c.camino_vacio()
        True
        """
        return self.pos >= len(self.cola)

    def camino_valor(self):
        """Devuelve la cantidad de flujo que llega a t. Si el camino no está
        terminado devuelve 0

        >>> c = Camino_aumentante()
        >>> c.add(3, 10, BACK)
        >>> c.add(2, 5, FORW)
        >>> c.quitar()
        >>> c.add(1, 4, FORW)
        >>> c.quitar()
        >>> c.quitar()
        >>> c.quitar()
        >>> c.camino_valor()
        4
        """
        return self.valor

    def imprimir_camino(self):
        """Esta función devuelve un string con el formato imprimible del camino
        acutal. Antes se debe llamar a camino_de_ancestros al menos una vez."""
        return self.camino_como_string

    def es_backward(self, x):
        """Devuelve True si el lado ancestro-x es backward.

        >>> c = Camino_aumentante()
        >>> c.add(3, 10, BACK)
        >>> c.add(2, 5, FORW)
        >>> c.es_backward(0)
        False
        >>> c.es_backward(2)
        False
        >>> c.es_backward(3)
        True
        """
        try:
            return (self.dict[x][2] == BACK)
        except:
            pass

    def devolver_corte(self):
        """Devuelve el contenido de la cola como una lista, será un corte sólo
        si se lo llama cuando t no está en la cola.

        >>> c = Camino_aumentante()
        >>> c.devolver_corte()
        [0]
        >>> c.add(3, 10, BACK)
        >>> c.add(2, 5, FORW)
        >>> c.quitar()
        >>> c.add(1, 4, FORW)
        >>> c.devolver_corte()
        [0, 3, 2, 1]
        """
        return self.cola

    def imprimir_corte(self):
        """Esta función devuelve el corte contenido en la cola en un string
        imprimible. Si es llamada después de que no hay más caminos aumentantes
        devuelve el corte minimal.

        >>> c = Camino_aumentante()
        >>> c.devolver_corte()
        [0]
        >>> c.add(3, 10, BACK)
        >>> c.add(2, 5, FORW)
        >>> c.quitar()
        >>> c.add(1, 4, FORW)
        >>> c.imprimir_corte()
        '{0, 3, 2, 1}'
        """
        s = ', '
        return '{' + s.join(str(n) for n in self.cola) + '}'


def _test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    _test()
